public class DP {
    public int climbStairs(int n) {
        if(n<=0) return 0;
        else if(n==1)return 1;
        else if(n==2)return 2;
        else {
            int data[]=new int[n+1];
            data[1]=1;
            data[2]=2;
            for (int i=3;i<=n;i++){
                data[i]=data[i-1]+data[i-2];
            }
            return data[n];
        }
    }

    public int maxProfit(int[] prices) {
        int len=prices.length;
        if(len<=1) return 0;
        int profit[]=new int[len-1];
        for (int i=0;i<len-1;i++){
            profit[i]=prices[i+1]-prices[i];
        }
        int sum=0;
        int temp=0;
        for (int i=0;i<len-1;i++){
            temp+=profit[i];
            if(temp>=0){
                if(temp>sum){
                    sum=temp;
                }
            }else {
                temp=0;
            }
        }
        return sum;
    }
    public int maxSubArray(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        int sum=Integer.MIN_VALUE;
        int temp=0;
        for (int i=0;i<nums.length;i++){
            temp=temp+nums[i];
            if(temp>0){
                if(temp>sum){
                    sum=temp;
                }
            }else {
                temp=0;
            }
        }
        return sum;
    }

    public int rob(int[] nums) {
        int n=nums.length;
        if(n==0)return 0;
        else if(n==1)return nums[0];
        else if(n==2) return nums[0]>nums[1]?nums[0]:nums[1];
        else {
            int dp[]=new int[n];
            dp[0]=nums[0];
            dp[1]=nums[1];
            dp[2]=dp[0]+nums[2];
            for (int i=3;i<n;i++){
                int pre=dp[i-2]>dp[i-3]?dp[i-2]:dp[i-3];
                dp[i]=pre+nums[i];
            }
            return dp[n-2]>dp[n-1]?dp[n-2]:dp[n-1];
        }

    }
}
